import java.sql.Array;
import java.sql.SQLOutput;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 * 至少有 三种 不同的方法可以解决这个问题。
 * 使用空间复杂度为 O(1) 的 原地 算法解决
 * User: xwl
 * Date: 2023-05-03
 * Time: 16:33
 */
public class Test2 {
    // 实现方法①
    public void rotate(int[] nums, int k) {
        // 实现方法①
        if (nums.length > 2) {
            // 旋转k次
            for (int i = 0; i < k; i++) {
                // 定义一个数用来交换
                int tmp = 0;
                // 旋转实现
                tmp = nums[1];
                nums[1] = nums[0];
                for (int j = 2; j < nums.length; j++) {
                    nums[0] = tmp;
                    tmp = nums[j];
                    nums[j] = nums[0];
                }
                nums[0] = tmp;
            }
        } else if (nums.length == 2) {
            if (k%2 == 1) {
                int tmp = nums[1];
                nums[1] = nums[0];
                nums[0] = tmp;
            }
        }
    }
    // 实现方法②
    public void rotate2(int[] nums, int k) {
        // 实现方法②
        if (nums.length == 2) {
            if (k % 2 == 1) {
                int tmp = nums[1];
                nums[1] = nums[0];
                nums[0] = tmp;
            }
        } else if (nums.length > 2) {
            // 定义一个n代表最终旋转数
            int n = k % nums.length;
            // 创建一个数组记录旋转后的数组
            int[] arr = new int[nums.length];
            for (int i = n; i < nums.length; i++) {
                arr[i] = nums[i - n];
            }
            for (int i = 1; i <= n; i++) {
                arr[n - i] = nums[nums.length - i];
            }
            // 拷贝
            for (int i = 0; i < nums.length; i++) {
                nums[i] = arr[i];
            }
        }
    }
    // 实现方法③
    // 利用三次逆置矩阵来实现
    // 先整体逆置
    // 再逆置数组 1 - k 位
    // 逆置数组其余位
    class Solution {
        public void rotate(int[] nums, int k) {
            k %= nums.length;
            reverse(nums, 0, nums.length - 1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.length - 1);
        }

        public void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start += 1;
                end -= 1;
            }
        }
    }
}
